//
//  ConvertBST.swift
//  LeetCodeSummary
//
//  Created by 彭西西 on 2020/9/21.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  538. 把二叉搜索树转换为累加树

import UIKit

/*
 538. 把二叉搜索树转换为累加树

 给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

  

 例如：

 输入: 原始二叉搜索树:
               5
             /   \
            2     13

 输出: 转换为累加树:
              18
             /   \
           20     13
 */

class ConvertBST: NSObject {
    var sum = 0
    
    func convertBST(_ root: TreeNode?) -> TreeNode? {
        
        guard root != nil else {
            return root
        }
        
        self.convertBST(root?.right)
        sum = sum + root!.val
        root?.val = sum
        
        self.convertBST(root?.left)
        
        return root
    }
}
